The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of m x n rooms laid out in a 2D grid. Our valiant knight was initially positioned in the top-left room and must fight his way through dungeon to rescue the princess.
The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.
Some of the rooms are guarded by demons (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight's health (represented by positive integers).
To reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.
Return the knight's minimum initial health so that he can rescue the princess.
Note that any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.
Example 1:
Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]] Output: 7 Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.
Example 2:
Input: dungeon = [[0]] Output: 1
Constraints:
m == dungeon.lengthn == dungeon[i].length1 <= m, n <= 200-1000 <= dungeon[i][j] <= 1000
Average Rating: 4.94 (34 votes)
Solution
Approach 1: Dynamic Programming
Overview
Like many problems with 2D grid, often the case one can apply either the technique of backtracking or dynamic programming.
Specifically, as it turns out, dynamic programming would work perfectly for this problem.
As a general pattern of dynamic programming, usually we construct a array of one or two dimensions (i.e.
dp[i]) where each element holds the optimal solution for the corresponding subproblem.
To calculate one particular element in the dp[i] array, we would refer to the previously calculated elements. And the last element that we figure out in the array would be the desired solution for the original problem.
Intuition
Following the above guideline, here is how we break down the problem into subproblems and apply the dynamic programming algorithm.
We are asked to calculate the minimal health point that the knight needs, in order to recuse the princess. The knight would move from the up-left corner of the grid to reach the down-right corner where the princess is located (e.g. as shown in the following graph).
Though the down-right corner is the final destination of the knight, we could start from the destination and deduce backwards the minimal health point that the knight would need at each step along the way.
So starting from the destination where the princess is locked down, as one can see from the following graph, the knight would need at least 6 health points to survive the damage (5 points) caused by the daemon.
Let us now take one step back. Before reaching the destination, there are two possible positions that the knight might situate, i.e. the one right above the destination so that the knight would take a down step, and the one to the left of the destination so that the knight would take a right step.
Let us look at the cell (denoted as cell U) right above the destination, as shown in the following graph. As we know now, the knight should possess at least 6 health points upon reaching the destination. Since at the cell U we have a magic org which would increase the health of knight by 1 point, the knight would just need to possess 5 health points at the arrival of cell U.
As another alternative to reach the destination, the knight might situate at the cell (denoted as cell L) to the left side of the destination, as shown in the following graph. In this case, similarly the knight would encounter a magic orb which would give him a 30-points boost on health. With this boost of health, it would be more than enough for the knight to survive the final daemon in the destination. As a result, the knight just needs to possess the minimal 1 health point upon entering the cell L.
Now that we have calculated the minimal health points that the knight would need before reaching the destination from two of the possible directions, we can carry on to one more step further from the destination. Let us look at the cell (denoted as cell UL) located at the up-left corner from the destination.
Following the same logic as we have seen in the above steps, we could obtain two values for this cell, which represent the minimal health points that the knight would need for each of the directions that he takes. As one can see from the following graph, at the cell UL, if the knight takes a right step next, he would need at least 5+10=15 health points, in order to rescue the princess at the end. If he takes a down step next, he would need at least 1+10=11 health points.
With all the 3 examples above, we conclude with the following graph where each cell is marked with two minimal health points respectively for each direction that the knight might take, except the destination cell. As one can see, starting from the up-left corner of the grid, the knight would only need 7 health points to rescue the princess.
Algorithm
Given the above intuition, let us see how we can model it with the general code pattern of dynamic programming algorithm.
First, we define a matrix dp[row][col], where the element dp[row][col] indicates the minimal health points that the knight would need, starting from the corresponding dungeon cell dungeon[row][col], in order to reach the destination.
In the following graph, we show what the dp matrix looks like, for the examples that we listed in the intuition section.
The main idea of the algorithm is clear: we need to calculate the values in the
dpmatrix. And the last value we calculate for the matrix would be the desired solution for the problem.
In order to calculate the values of dp matrix, we start from the down-right corner of the dungeon, and walk following the orders of from-right-to-left and from-down-to-up. Along with each cell in the dungeon, we calculate the corresponding value of dp[row][col] in the matrix.
The value of dp[row][col] is determined by the following conditions:
-
If possible, by taking the right step from the current dungeon cell, the knight might need
right_healthhealth points. -
If possible, by taking the down step from the current dungeon cell, the knight would might
down_healthhealth points. -
If either of the above two alternatives exists, we then take the minimal value of them as the value for
dp[row][col]. -
If none of the above alternatives exists, i.e. we are at the destination cell, there are two sub-cases:
-
If the current cell is of magic orb, then 1 health point would suffice.
-
If the current cell is of daemon, then the knight should possess one health point plus the damage points that would be caused by the daemon.
-
Complexity
-
Time Complexity: O(M⋅N) where M⋅N is the size of the dungeon. We iterate through the entire dungeon once and only once.
-
Space Complexity: O(M⋅N) where M⋅N is the size of the dungeon. In the algorithm, we keep a dp matrix that is of the same size as the dungeon.
Approach 2: Dynamic Programming with Circular Queue
Intuition
In the above dynamic programming algorithm, there is not much we can do to optimize the time complexity, other than reducing the costy condition checks with some tricks on the initial values of the dp matrix.
On the other hand, we could reduce the space complexity of the algorithm from O(M⋅N) to O(N) where N is the number of columns.
First of all, let us flatten the dp matrix into 1D array, i.e. dp[row][col] = dp[row * N + col].
As one might notice in the above process, in order to calculate each
dp[i], we would refer to at most two previously calculateddpvalues, i.e.dp[i-1]anddp[i-N]. Therefore, once we calculate the value fordp[i], we could discard all the previous values that are beyond the range ofN.
The above characteristics of the dp array might remind you the container named CircularQueue which could serve as a sliding window to scan a long list.
Indeed, we could use the CircularQueue to calculate the dp array, as we show in the above graph. At any moment, the size of the CircularQueue would not exceed the predefined capacity, which would be N in our case. As a result, we reduce the overall space complexity of the algorithm to O(N).
Algorithm
Complexity
-
Time Complexity: O(M⋅N) where M⋅N is the size of the dungeon. We iterate through the entire dungeon once and only once.
-
Space Complexity: O(N) where N is the number of columns in the dungeon.
April 4, 2020 3:15 AM
hi @merkle_tree In this case, I would say no. You see, the basic idea of Dynamic Programming is to start from the "bottom case" (pun intended), and then progress towards the final result. In our case, the value at the up-left corner of the grid (location [0,0]) is actually the desired "destination", which is exactly why we cannot start from the point.
Amazing article, thank you! I'm missing the advantage of starting in the bottom right corner -- could we also solve this if we started at 0,0 as well?
Hi @liaison ,
I tried solving this problem with DP using the top down approach i.e. start from initial position in upper left position and then try to reach from that position to either right or down and calculating the minimum life required at each step. Finally, the bottom right position in DP matrix will be my answer but I am getting wrong answer for that. Can you please explain why this approach is not correct in this problem ?
Nice explanation, BUT
Why does bottom up DP work when initiated from the bottom right cell, and not from the top left cell?
Any intuition/visuals would really help.
I was only able to solve this problem using the former approach, but why is the DP not symmetrical as with other problems (i.e maximum subarray)?
why this problem is tagged as Binary Search /
December 1, 2020 6:29 AM
Amazing article. I loved it. Thank you :)
Last Edit: June 22, 2020 8:04 AM
To anyone (else) who's intuition led them to think of Bellman Fords because of the negative weights, it's not a trivial application of the algorithm given the dungeon is an N by M matrix.
Turning this matrix into a graph would require the creation of a root node and then figuring out how to associate the weights in the matrix to each node. This would exhaust the time and space explained in the DP solutions above without even giving the solution.
Staff feedback welcome :)
x
class Solution {public: int calculateMinimumHP(vector<vector<int>>& dungeon) { int m = dungeon.size(); int n = dungeon[0].size(); vector<vector<int>> dp(m+1, vector<int>(n+1, INT_MAX)); // for bottom right col checks dp[m-1][n] = 1; dp[m][n-1] = 1; for(int i=m-1;i>=0;i--) { for(int j=n-1;j>=0;j--) { // either come from down or right int hp = min(dp[i+1][j], dp[i][j+1]) - dungeon[i][j]; // if we are currently in magic orb, (we need -ve hp to survuve, hp should be set to 1) hp = max(hp, 1); dp[i][j] = hp; } } return dp[0][0]; }};







